package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.TreeNode;
import com.shuo.dsa.test.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 求树的最小深度:
 *      思路: BFS找出第一个左右孩子为空的Node并返回其深度
 *
 * Given a binary tree, find its minimum depth.The minimum depth
 * is the number of nodes along the shortest path from the root node
 * down to the nearest leaf node
 */
public class MinDepthNode {
    public static void main(String[] args) {
        TreeNode root = TreeUtil.createTree(20);
        System.out.println(getMinDepth(root));
        TreeUtil.bfs(root);
    }


    public static int getMinDepth(TreeNode node) {
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode a = queue.poll();
                if (a.left != null)
                    queue.offer(a.left);
                if (a.right != null)
                    queue.offer(a.right);
                if (a.left == null && a.right == null)
                    return depth;
            }
        }
        return 0;
    }
}
